package com.mgq.algorithm.array;

/**
 * 求逆序对
 * 3,2,4,5,0,9
 * 左边数大于右边数,就构成一个逆序对
 * 3,2 ,3 0
 * 2,0
 * 4,0
 * 5,0
 * 求逆序对个数
 */
public class ReverseOrder {
    public static void main(String[] args) {
        int[] array=new int[]{3,2,4,5,0};
        int process = process(array, 0, array.length - 1);
        System.out.println(process);
    }

    private static int process(int[] array, int L, int R) {
        if (L == R) {
            return 0;
        }
        int mid = L + ((R - L) >> 1);
        return process(array, L, mid) + process(array, mid + 1, R)
                + merge(array, L, mid, R);
    }

    public static int merge(int[] array, int L, int M, int R) {
        int[] help = new int[R - L + 1];
        int p1 = L;
        int p2 = M + 1;
        int i = 0;
        int count=0;
        while (p1 <= M && p2 <= R) {
            count+=array[p1] > array[p2]?(M-L+1):0;
            help[i++] = array[p1] > array[p2] ? array[p2++] : array[p1++];
        }
        while (p1 <= M) {
            help[i++] = array[p1++];
        }
        while (p2 <= M) {
            help[i++] = array[p2++];
        }
        for (int j = 0; j <help.length ; j++) {
            array[L + j] = help[j];
        }
        return count;
    }
}
